The present invention relates to data processing and more specifically to methods and apparatuses for performing image compression.
Without image compression, the transmission of images recquires an unacceptable bandwidth in many applications. As a result, methods of compressing images have been the subject of numerous research publications. Image compression schemes convert an image consisting of a two-dimensional array of pixels into a sequence of bits which are to be transmitted over a communication link. Each pixel represents the intensity of the image at a particular location therein. The transmission link may be an ordinary telephone line.
Consider an image comprising a gray-scale representation of a photograph at a resolution of 1000.times.1000 lines. Each pixel typically consists of 8 bits which are used to encode 256 possible intensity levels at the corresponding point on the photograph. Hence, without compression, transmission of the photograph requires that 8 million bits be sent over the communication link. A typical telephone line is capable of transmitting about 9600 bits per second; hence the picture transmission would require more than 10 minutes. Transmission times of this magnitude are unacceptable.
As a result, image compression systems are needed to reduce the transmission time. It will also be apparent to those skilled in the art that image compression systems may also be advantageously employed in image storage systems to reduce the amount of memory needed to store one or more images.
Image compression involves transforming the image to a form which can be represented in fewer bits without losing the essential features of the original image. The transformed image is then transmitted over the communication link in question and the inverse transformation applied at the receiver to recover the image or a reasonable facsimile thereof.
The degree to which the recovered image differs from the original image is referred to as the distortion of the image. Distortion is normally measured as the root mean square of the pixel by pixel differences of the original and recovered images. As will be discussed in more detail below, images with the same level of distortion may differ greatly in their subjective distortion, i.e., distortion as perceived by an observer. Hence, choosing compression algorithms based on such measures of distortion may lead to methods that achieve less than the optimum result as viewed from the human perspective.
The compression of an image typically requires two steps. In the first step, the image is transformed to a new representation in which the correlation between adjacent pixels is reduced. This transformation is usually completely reversible, that is, no information is lost at this stage. The number of bits of data needed to represent the transformed image are at least as large as that needed to represent the original image. The purpose of this transformation is to provide an image representation which is more ideally suited to known compression methods.
In the second step, referred to as quantization, each pixel in the transformed image is replaced by a value which is represented in fewer bits, on average, than the original pixel value. In general, the original gray scale is replaced by a new scale which has coarser steps and hence can be represented in fewer bits. The new gray scale typically has levels in which the different steps are of different size. The new gray scale is calculated from the statistical distribution of the pixel values in the transformed image.
The quantization process typically results in loss of information, since there will always be at least two different pixel levels in the original gray scale that will be assigned to the same level in the new gray scale. For example, a single level in the new gray scale might correspond to levels 200 through 210 in the above mentioned 256-level gray scale. Hence, the ability to make distinctions based on differences in pixel intensity in this range will be lost, since, after quantization, all pixels in this range will have been assigned the same level in the new gray scale. This loss of information will be referred to as quantization errors.
The quantized image resulting from the above two steps is often further coded for transmission over the communication link in question. This coding is completely reversible. Its purpose is to provide a more compact representation of the quantized picture At the other end of the communication link, the coded image is decoded, the quantization transformation is reversed and the inverse of the first transformation performed on the resulting image to provide a reconstructed image.
The extent to which the reconstructed image differs from the original image will, in general, depend on the above mentioned first transformation and on the manner in which it interacts with the quantization system. In the following discussion, the first transformation in question will be referred to as the image transformation. In general, the image transformation is equivalent to calculating the coefficients of a series expansion of the image in some set of expansion functions in a manner analogous to calculating the Fourier transform of a one-dimensional function. These coefficients are then quantized and transmitted. At the receiving end, the image is reconstructed by effectively multiplying the particular functions in question by the transmitted coefficients and then summing the results.
The extent to which a quantization error causes an error in the reconstructed image will depend on the expansion functions in question. It is useful to define two classes of functions, those with compact support and those with non-compact support. For the purposes of this discussion, a function has compact support if it is zero outside some limited region of the image.
If the expansion functions have non-compact support, then a quantization error can effect a very large portion of the reconstructed image. Each pixel of the reconstructed image may be viewed as being calculated by summing contributions from a number of expansion functions multiplied by the transmitted coefficients. The number of such functions that contribute to the intensity of a given pixel in the reconstructed image depends on the compactness of the function set chosen. The less compact the expansion set, the larger the number of functions that can contribute to each point on the reconstructed image Thus, the probability that a quantization error will be present is greater. In addition, an error in a coefficient which multiplies a function in a non-compact expansion set will affect many more pixels since the function in question has a larger spatial extent.
Prior art image transformations utilize non-compact expansion function sets. Hence, quantization errors tend to affect the entire image In addition, the errors in question tend to be very obvious to human observers of the reconstructed images. These errors produce artifacts such as stripes in the image. To lessen the visual impact of such artifacts, prior art systems often incorporate low-pass filters. However, these filters often remove important picture detail. Thus, this method of eliminating the artifacts is less than ideal. In addition, the low-pass filtering requires additional computational capacity in the image compression apparatus. This additional capacity increases the cost of the apparatus in question.
The image transformation circuitry is a significant cost factor in image compression apparatuses. The required computational expense clearly depends on the image transformation selected. Hence, an image compression apparatus which utilizes an image transformation which requires less computation than prior art image transformation would be very advantageous.
Accordingly, it is an object of the present invention to provide an improved image compression method and apparatus.
It is a further object of the present invention to provide an image compression apparatus and method which utilizes an image transformation based on a set of expansion functions which have compact support.
It is yet another object of the present invention to provide an image compression apparatus and method which requires less computational capacity than prior art image compression systems.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the present invention and the accompanying drawings.